/*************************************************************************
    > File Name: wordladder_dfs.cpp
    > Author: Wulei
    > Mail: wlinpisces@gmail.com 
    > Created Time: Sun 02 Mar 2014 11:54:09 PM
 ************************************************************************/

#include<iostream>
using namespace std;

class Solution
{
public:
    int Helper(string current, string dest, unordered_set<string>& dict,
            bool isFirstCall)
    {
        int ret = INT_MAX;
        if (current == dest && !isFirstCall)
            return 1;
        if (dict.empty())
            return INT_MAX;
        for (int i = 0; i < current.size(); i++)
            for (int j = 'a';j <= 'z'; j++){
                if (j == current[i])
                    continue;
                char temp = current[i];
                current[i] = j;
                if (dict.count(current) > 0){
                    dict.erase(current);
                    int rettemp = Helper(current, dest, dict);
                    if(rettemp != INT_MAX)
                        ret = min(rettemp + 1, ret);
                    dict.insert(current);
                }
            }
        return ret;
    }
    int ladderlength(string start, string end, unordered_set<string> &dict)
    {
        if (start.size() != end.size())
            return 0;
        if (start.empty() || end.empty() || dict.empty)
            return 0;
        bool isEqual = false;
        if (start == end)
            isEqual = true;
        int temp = Helper(start, end, dict, isEqual);
        if(temp == INT_MAX)
            return 0;
        else
            return temp;
    }
}
